
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1630. -- [Usaco2007 Demo]Ant Counting -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1630: [Usaco2007 Demo]Ant Counting</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>81&nbsp;&nbsp;<span class=green>Solved: </span>49<br>[<a href='submitpage.php?id=1630'>Submit</a>][<a href='problemstatus.php?id=1630'>Status</a>][<a href='bbs.php?id=1630'>Discuss</a>]</center><h2>Description</h2><div class=content>Bessie was poking around the ant hill one day watching the ants
march to and fro while gathering food.  She realized that many of
the ants were siblings, indistinguishable from one another.  She
also realized the sometimes only one ant would go for food, sometimes
a few, and sometimes all of them. This made for a large number of
different sets of ants!

Being a bit mathematical, Bessie started wondering.  Bessie noted
that the hive has T (1 <= T <= 1,000) families of ants which she
labeled 1..T (A ants altogether).  Each family had some number Ni
(1 <=  Ni <= 100) of ants.

How many groups of sizes S, S+1, ..., B (1 <= S <= B <= A) can be
formed?

While observing one group, the set of three ant families was seen
as {1, 1, 2, 2, 3}, though rarely in that order. The possible sets
of marching ants were:

  3 sets with 1 ant:  {1} {2} {3}
  5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}
  5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
  3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}
  1 set  with 5 ants: {1,1,2,2,3}

Your job is to count the number of possible sets of ants given the
data above.

//有三个家庭的ANT，共五只，分别编号为1,2,2,1,3，现在将其分为2个集合及3集合，有多少种分法
</div><h2>Input</h2><div class=content>* Line 1: 4 space-separated integers: T, A, S, and B

* Lines 2..A+1: Each line contains a single integer that is an ant
        type present in the hive

</div><h2>Output</h2><div class=content>* Line 1: The number of sets of size S..B (inclusive) that can be
        created. A set like {1,2} is the same as the set {2,1} and
        should not be double-counted. Print only the LAST SIX DIGITS
        of this number, with no leading zeroes or spaces.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 5 2 3<br />
1<br />
2<br />
2<br />
1<br />
3<br />
<br />
INPUT DETAILS:<br />
<br />
Three types of ants (1..3); 5 ants altogether.  How many sets of size 2 or<br />
size 3 can be made?<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>10<br />
<br />
OUTPUT DETAILS:<br />
<br />
5 sets of ants with two members; 5 more sets of ants with three members<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1630'>Submit</a>][<a href='problemstatus.php?id=1630'>Status</a>][<a href='bbs.php?id=1630'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
